#include<bits/stdc++.h>
#define lol long long
using namespace std;
lol gcd(lol a,lol b){ return b?gcd(b,a%b):a; }
lol isprime(lol val){
	if(val==0||val==1) return 0;
	if(val==2) return 1;
	for(lol i=2;i*i<=val;++i){
		if(val%i==0) return 0;
	}
	return 1;
}
lol counter;
lol KSM(lol a,lol b,lol n){
	lol result=1; lol tmp=a%n; counter = 0;
	while(b){
		if(b&1) { result=result*tmp%n; ++counter; }
		tmp=tmp*tmp%n;
		b>>=1;
	}
	return result%n;
}
int main(){
	lol a,m,n;
	scanf("%lld%lld%lld",&a,&m,&n);
	if(m>n and isprime(n) and gcd(a,n)==1 ) m%=n-1; 
	lol answer=KSM(a,m,n);
	printf("%lld %lld\n",answer,counter);
	return 0;
}
